import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by zh on 17/1/25.
 */

class Bean {
    private String name;
    private String[] depends;


    public Bean(String name, String[] depends) {
        this.name = name;
        this.depends = depends;
    }

    public String getName() {
        return name;
    }

    public String[] getDepends() {
        return depends;
    }

    @Override
    public String toString() {
        return name;
    }
}

public class DependOn {


    public static void main(String[] args) {
        Bean e = new Bean("1e", new String[]{"3a", "4c"});
        Bean a = new Bean("3a", new String[0]);
        Bean b = new Bean("2b", new String[]{"3a"});
        Bean c = new Bean("4c", new String[]{"3a", "2b", "5d"});
        Bean d = new Bean("5d", new String[]{"3a", "4c"});

        List<Bean> beanList = new ArrayList<>();
        beanList.add(a);
        beanList.add(b);
        beanList.add(c);
        beanList.add(d);
        beanList.add(e);
        sort(beanList);
    }

    public static void sort(List<Bean> beanList) {
        Map<String, Bean> beanMap = new HashMap<>();

        beanList.forEach((b) -> beanMap.put(b.getName(), b));

        System.out.println(beanMap);

        List<Bean> sortedList = new ArrayList<>();
        for (Map.Entry<String, Bean> entry : beanMap.entrySet()) {
            getBeanDepends(beanMap, sortedList, entry.getKey());
        }
        System.out.println(sortedList);
    }

    private static void getBeanDepends(Map<String, Bean> beanMap, List<Bean> sortedList, String dependName) {
        Bean bean = beanMap.get(dependName);
        String[] depends = bean.getDepends();
        if (sortedList.contains(bean)) {
            System.out.println("依赖已存在:" + dependName);
            return;
        }
        for (String depend : depends) {
            if (!beanMap.containsKey(depend)) {
                System.out.println("依赖不存在:" + depend);
                continue;
            }
            if (sortedList.contains(beanMap.get(depend))) {
                System.out.println("依赖已存在:" + depend);
                continue;
            }

            getBeanDepends(beanMap, sortedList, depend);
        }
        sortedList.add(bean);
    }


}
